CF815C Karen and Supermarket

因为使用优惠劵就必须买这件商品，我们可以将优惠劵的关系看成一棵树。

令 $dp[u][i][0/1]$ 表示 以 $u$ 为根的子树 ， 购买 $i$ 件商品 ， $u$ 是否使用优惠劵的最小花费。

边界条件：$dp[u][0][0]=0,dp[u][1][0]=c[u],dp[u][1][1]=c[u]-d[u]$

注意：$dp[u][1][0]$ 是不成立的，因为使用优惠券就必须购买商品，其余设为极大值。

然后有如下转移：

$\begin{cases} dp[ u ][ j + k ][ 0 ] = min( dp[ u ][ j ][ 0 ] + dp[ v ][ k ][ 0 ] )\\ dp[ u ][ j + k ][ 1 ] = min( dp[ u ][ j ][ 1 ] + min( dp[ v ][ k ][ 0 ] , dp[ v ][ k ][ 1 ] ) ) \end{cases}$

最后看满足 $min(dp[1][k][0],dp[1][k][1])\le b$ 的最大的 $k$ 即可。

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

template<typename _T>
void Read( _T &x ) {
	x = 0; int f = 1;
	char s = getchar( );
	for( ; s < '0' || s > '9' ; s = getchar( ) ) f = s == '-' ? -f : f;
	for( ; s >= '0' && s <= '9' ; s = getchar( ) ) x = x * 10 + s - '0';
	x *= f;
}
template<typename _T>
void Write( _T x ) {
	if( x < 0 ) putchar('-') , x = -x;
	if( x >= 10 ) Write( x / 10 );
	putchar( x % 10 + '0' );
} 

const int MAXN = 5000;
int n , m , fa , c[ MAXN + 5 ] , d[ MAXN + 5 ] , Size[ MAXN + 5 ];
int dp[ MAXN + 5 ][ MAXN + 5 ][ 2 ];
vector< int > Graph[ MAXN + 5 ];

void dfs( int u ) {
	Size[ u ] = 1;
	dp[ u ][ 0 ][ 0 ] = 0 , dp[ u ][ 1 ][ 0 ] = c[ u ];
	dp[ u ][ 1 ][ 1 ] = c[ u ] - d[ u ];
	
	for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
		int v = Graph[ u ][ i ];
		dfs( v ); 
		
		for( int j = Size[ u ] ; j >= 0 ; j -- ) //注意循环顺序，不然会超时
			for( int k = 0 ; k <= Size[ v ] ; k ++ ) {
				dp[ u ][ j + k ][ 0 ] = min( dp[ u ][ j + k ][ 0 ] , dp[ u ][ j ][ 0 ] + dp[ v ][ k ][ 0 ] );
				dp[ u ][ j + k ][ 1 ] = min( dp[ u ][ j + k ][ 1 ] , dp[ u ][ j ][ 1 ] + min( dp[ v ][ k ][ 0 ] , dp[ v ][ k ][ 1 ] ) );
			}
		Size[ u ] += Size[ v ];
	}
}

int main( ) {
	Read( n ) , Read( m );
	for( int i = 1 ; i <= n ; i ++ ) {
		Read( c[ i ] ) , Read( d[ i ] );
		if( i >= 2 ) {
			Read( fa );
			Graph[ fa ].push_back( i );
		}
	}
	
	memset( dp , 0x3f , sizeof( dp ) );
	dfs( 1 );
	
	for( int i = n ; i >= 0 ; i -- )
		if( dp[ 1 ][ i ][ 0 ] <= m || dp[ 1 ][ i ][ 1 ] <= m ) {
			Write( i ) , putchar('\n');
			return 0;
		} 
	return 0;
}